#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
	int maximalRectangle(vector<vector<char>>& matrix)
	{
		if (!matrix.size()) return 0;

		int rowLen = matrix[0].size();
		short matrixVal[matrix.size() + 2][rowLen]; memset(matrixVal, -1, sizeof(matrixVal));
		for (int col = 1, lenCol = matrix.size() + 1; col < lenCol; col++) {
			matrixVal[col][0] = matrix[col - 1][0] - '0';
			for (int row = 1, lenRow = matrix[0].size(); row < lenRow; row++) {
				matrixVal[col][row] = matrix[col - 1][row] - '0';
				if (matrixVal[col][row]) matrixVal[col][row] += matrixVal[col][row - 1];
			}
		}

		int res = 0; deque<int> aux;

		for (int row = matrix[0].size() - 1; row >= 0; row--) {
			aux.clear(); aux.emplace_back(0);
			for (int col = 1, len = matrix.size() + 2; col < len; col++) {
				while (matrixVal[col][row] < matrixVal[aux.back()][row]) {
					int high = matrixVal[aux.back()][row]; aux.pop_back();
					int width = col - 1 - aux.back();
					res = max(res, high * width);
				}
				aux.emplace_back(col);
			}
		}

		return res;
	}
};

int main()
{
	return 0;
}
